Graphe de Petersen

Graphe de Petersen
Schéma classique du graphe de Petersen, sous la forme d'un pentagone et d'un pentagramme concentriques, reliés par cinq rayons.
Nombre de sommets	10
Nombre d'arêtes	15
Distribution des degrés	3-régulier
Rayon	2
Diamètre	2
Maille	5
Automorphismes	120 (S5)
Nombre chromatique	3
Indice chromatique	4
Propriétés	Cage Cubique Distance-transitif Distance-unité Fortement régulier Hypohamiltonien Graphe de Moore Snark Symétrique
modifier

Le graphe de Petersen est, en théorie des graphes, un graphe particulier possédant 10 sommets et 15 arêtes.

Il s'agit d'un petit graphe qui sert d'exemple et de contre-exemple pour plusieurs problèmes de la théorie des graphes. Il porte le nom du mathématicien Julius Petersen, qui l'introduisit en 1898 en tant que plus petit graphe cubique sans isthme dont les arêtes ne peuvent être colorées avec trois couleurs^[1]. Il a cependant été mentionné par Alfred Kempe pour la première fois 12 ans auparavant, en 1886^[2].

Donald Knuth explique dans The Art of Computer Programming que le graphe de Petersen est « une configuration remarquable qui sert de contre-exemple à de nombreuses prédictions optimistes sur ce qui devrait être vrai pour tous les graphes^[3] ».